#Algorithm #Algorithm_Levenshtein #Algorithm_DP

0. 관련 문제

72. Edit Distance

1. Levenshtein Algorithm

=> 두 대상간의 유사도를 계산할 때 사용하는 알고리즘

더 정확히 말하면, 어떤 대상 A를 변경해서 B를 만든다고 했을 때, 변경을 실행한 가장 적은 횟수를 구하는 알고리즘이다. 문자열을 대표적인 예로 들 수 있는데, 'kotlin' 이라는 단어를 'lint'로 변경할 때에 몇번의 조작이 들어가야 하냐는 것을 구할 때 사용할 수 있다.

Levenshtein Distance(Edit Distance, 편집 거리 알고리즘), leesumin 포스트에 자세한 설명이 잘 되어있다.

2. 문자열 최소 변경 횟수 구하기

여기서 '변경'이라는 조작은 3가지 이다. 삽입, 삭제, 대체가 그것이다.

• 삽입(Insert): ab -> abc로 변경하기 위해서는 ab에 c를 삽입해주면 된다.
• 삭제(Delete): abc -> ab로 변경하기 위해서는 abc에서 끝의 c를 삭제해 주면 된다.
• 대체(Replace): abc -> abd로 변경하기 위해서는 abc에서 끝의 c를 d로 바꿔주면 된다.
  이 조작들을 1회의 변경으로 계산하여 문자열A가 문자열B가 되도록 만드는 변경의 최소 횟수를 구할 때 이 알고리즘을 사용할 수 있다.

2-1. Edit Distance Array 이해하기

Levenshtein Distance, Claire Lee 포스트에 그림으로 설명이 잘 되어 있다.

S1 -> S2로 변경된다고 했을 때 min distance를 구하는 memoization 배열의 공식은 다음과 같다.
S1이 col에 위치하고, S2가 row에 위치한다고 했을 때, 삽입, 삭제, 대체의 연산 횟수는 다음과 같다.

• 삽입(Insert): memoizationArray[row-1][col]+1
• 삭제(Delete): memoizationArray[row][col-1]+1
• 대체(Replace): memoizationArray[row-1][col-1]+1

내가 생각했을 때 각각의 의미는 다음과 같다.

• 삽입: S2는 변화가 없고 S1은 S2보다 하나 추가되어서 위치가 하나 옮겨졌다. 결과에 추가 연산 횟수 1을 더해
• 삭제: S2는 다음 자리로 간 상태에서 S1은 삭제되어서 위치가 S2보다 하나 옮겨졌다. 결과에 삭제 연산 횟수 1을 더해
• 대체: S2와 S1은 둘 다 변화가 있어서 변화가 없는것과 마찬가지다. 결과에 대체 연산 횟수 1을 더해